题解 P2602 [ZJOI2010]数字计数

发表于 | 更新于

题意：给定两个正整数$a$和$b$，求在$[a,b]$中的所有整数中，每个数字各出现了多少次。

定义状态$f[i][j][k]$表示以$j$开头的$i$位数$k$出现的次数

状态转移方程

$f[i][j][k]=\sum\limits_{p=0}^{9}f[i-1][p][k]+(10^{i-1}* [j==k])$

(解释：$i$位数除去最高位就是$i-1$位数，所以要加上所以$i-1$位数的出现次数$(\sum\limits_{p=0}^{9}f[i-1][p][k])$，再加上最高位出现的次数$(10^{i-1}* [j==k])$

求$A$到$B$之间出现的次数即使就$(1$~$B)-(1$~$(A-1))$的次数

$dp$完了后要开始统计了，首先特判$0$的情况，然后计算出这个数的位数$pos$，所以位数比这个数小的都可以统计答案。由于不能有前导$0$，所以最高位要从$1$枚举到$9$，再枚举所有$i$位数，从最高位枚举到最低位，只要小于当前位的都可以统计(注意等于不可以统计)，再统计一下当前位的贡献，最后还要减去前导$0$的情况

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
#include <bits/stdc++.h>
#define int long long
#define sqr(x) ((x)*(x))
using namespace std;
inline int read(){
    int x=0,w=0;char ch=getchar();
    while (!isdigit(ch))w|=ch=='-',ch=getchar();
    while (isdigit(ch))x=(x<<1)+(x<<3)+ch-'0',ch=getchar();
    return w?-x:x;
}
int f[30][40][40],ans[300],poow[200];
void make(int x,int d){
    if (!x){
        ans[0]+=d;return;//0单独特判 
    }
    int o=x,poos=0;
   while(o){++poos;o/=10;}//算出这个数的位数 
    for (int i=1;i<poos;++i)//位数比这个数小的都可以统计答案 
        for (int j=1;j<=9;++j)//从1开始循环是因为开头不能为0 
            for (int k=0;k<=9;++k)
                ans[k]+=f[i][j][k]*d;
    for (int i=poos;i>=1;--i){
        int now=x/poow[i-1];x%=poow[i-1];
        for (int j=0;j<now;++j){//比当前位小的都要统计答案 
            for (int k=0;k<=9;++k)
                ans[k]+=f[i][j][k]*d;
        }
        ans[now]+=(x+1)*d;//当前位也要统计答案(x+1)是因为有后面都是0的情况)
    } 
    for (int i=0;i<=9;++i)ans[i]-=f[poos][0][i]*d;//减去前导0 
    ans[0]+=d;
//0要特殊处理，因为减去前导0时把0一起统计了
} 
signed main(){
    int a=read(),b=read();
    int cnt=13;
    poow[0]=1;for (int i=1;i<=cnt;++i)poow[i]=poow[i-1]*10;//预处理10的幂次
    for (int j=0;j<=9;++j)f[1][j][j]=1;
    for (int i=2;i<=cnt;++i)
        for (int j=0;j<=9;++j){
            for (int k=0;k<=9;++k)
                for (int p=0;p<=9;++p)
                    f[i][j][k]+=f[i-1][p][k];
            f[i][j][j]+=poow[i-1];
        }
    make(b,1);
    make(a-1,-1);//类似前缀和 
    for (int i=0;i<=9;++i)
        printf("%lld ",ans[i]);
    return 0;
}